package leetcode;

import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 叶子相似的树
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.10
 */

public class T872 {
    public static void main(String[] args) {
        int[] root1 = {3, 5, 1, 6, 2, 9, 8, -1, -1, 7, 4};
        int[] root2 = {3, 5, 1, 6, 7, 4, 2, -1, -1, -1, -1, -1, -1, 9, 8};


        TreeNode rootNode1 = buildTree(root1, null, 0);
        TreeNode rootNode2 =    buildTree(root2, null, 0);


        T872 t872 = new T872();
        System.out.println(t872.leafSimilar(rootNode1, rootNode2));
    }

    //构建完全二叉树
    public static TreeNode buildTree(int[] root, TreeNode rootNode, int index) {
        if (index >= root.length) {
            return null;
        }
        if (rootNode != null) {
            rootNode.val = root[index];
        } else {
            rootNode = new TreeNode(root[index]);
        }

        if (2 * index + 1 < root.length && root[2 * index + 1] != -1) {
            rootNode.left = new TreeNode();
            buildTree(root, rootNode.left, 2 * index + 1);
        }
        if (2 * index + 2 < root.length&& root[2 * index + 2] != -1) {
            rootNode.right = new TreeNode();
            rootNode.right = buildTree(root, rootNode.right, 2 * index + 2);
        }

        return rootNode;
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List list1 = new ArrayList();
        List list2 = new ArrayList();
        getAllLeaf(root1, list1);
        getAllLeaf(root2, list2);

        return list1.equals(list2);
    }

    public void getAllLeaf(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
        } else {
            getAllLeaf(root.left, list);
            getAllLeaf(root.right, list);
        }

    }
}
